package com.core;
/**
 * 二叉堆优化寻路驱动
 * @author hongxiao.zhuang
 * @date 2013-7-8
 */
public class BinaryHeapDrive 
{
	/**
	 * 地图数据
	 */
	char[][] data;
	
	public void find(int startX, int startY, int endX, int endY)
	{
	}
	
	/**
	 * 二叉堆添加元素
	 * @param arr				评估值二叉堆
	 * @param binaryHeapSize	二叉堆中的元素数量
	 * @param element			新添加的元素
	 * @return 					二叉堆长度
	 * @create					2013-7-8 hongxiao.zhuang
	 */
	int addElement(int[] arr, int binaryHeapSize, int element)
	{
		/*更新二叉堆长度*/
		binaryHeapSize++;
		
		/*把新元素添加到尾部*/
		arr[binaryHeapSize] = element;
		
		/*声明变量j, 作用于元素的父节点*/
		int j = 0;
		for (int i = arr.length; i > 0; i = j) 
		{
			/*获得父节点下标*/
			j = i / 2;
			
			/*如果父节点元素评估值比新元素大, 则调换位置*/
			if(arr[i] < arr[j])
			{
				exchangeIndex(arr, i, j);
				continue;
			}
			
			break;
		}
		
		/*返回新的二叉堆长度*/
		return binaryHeapSize;
	}
	
	/**
	 * 删除二叉堆元素
	 * @param arr				评估值二叉堆
	 * @param binaryHeapSize	二叉堆的长度
	 * @return					二叉堆长度
	 * @create 					2013-7-8 庄宏晓
	 */
	int delElement(int[] arr, int binaryHeapSize)
	{
		/*删除第一个元素, 替换上最后一个元素*/
		arr[1] = arr[binaryHeapSize];   
		/*更新二叉堆长度*/
		binaryHeapSize--;
		
		/*声明变量j, 作用于元素的子节点*/
		for (int i = 1; i <= binaryHeapSize;) 
		{
			/*获得两个子节点*/
			int child_1 = arr[i*2];
			int child_2 = arr[i*2+1];
			
			/*获得评估值最低的子节点*/
			int child = child_1 <= child_2 ? child_1 : child_2;
			
			/*如果元素比子元素评估值更低, 则变换位置*/
			if(arr[i] < arr[child])
			{
				exchangeIndex(arr, i, child);
				i = child_1;
			}
			else
			{
				break;
			}
		}
		
		/*返回二叉堆长度*/
		return binaryHeapSize;
	}
	
	/**
	 * 二叉堆元素的调换
	 * @param arr				二叉堆
	 * @param index_1			位置1
	 * @param index_2			位置2
	 * @create 2013-7-8			hongxiao.zhuang
	 */
	void exchangeIndex(int[] arr, int index_1, int index_2)
	{
		int temp = arr[index_1];
		arr[index_1] = arr[index_2];
		arr[index_2] = temp;
	}
}
